package com.example.tree;

import java.util.Deque;
import java.util.LinkedList;

public class Leetcode559_NTreeMaxDepth {
    public static void main(String[] args) {

    }


    /**
     * 解法二:深度优先遍历
     * @param root
     * @return
     */
    public int maxDepth2(Node root) {

        if (root == null)
            return 0;
        int maxDepth = 0;

        for (int i = 0; i < root.children.size(); i++) {
            maxDepth = Math.max(maxDepth, maxDepth(root.children.get(i)));
        }
        return maxDepth + 1;

    }

    /**
     * 解法一:广度优先遍历(BFS)
     *
     * @param root
     * @return
     */
    public int maxDepth(Node root) {
        if (root == null) return 0;

        int maxDepth = 0;
        Deque<Node> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();

            while (size > 0) { // 完成一层的遍历
                Node node = queue.poll();
                System.out.println(node.val);
                for (int i = 0; i < node.children.size(); i++) {
                    queue.offer(node.children.get(i));
                }
                size--;
            }
            ++maxDepth;
        }

        return maxDepth;
    }



}
